"""
类：MinStack - 实现一个支持获取最小值的栈

Args:
    st: 使用列表实现的栈，每个元素是一个元组 (当前值, 当前最小值)

Returns:
    push: 无返回值
    pop: 无返回值
    top: 返回栈顶元素的值
    getMin: 返回当前栈中的最小值

Time:
    push: O(1)
    pop: O(1)
    top: O(1)
    getMin: O(1)

Space: O(n) - 需要存储所有元素及其对应的最小值
"""
class MinStack:

    def __init__(self):
        self.st = [(0, inf)]

    def push(self, val: int) -> None:
        self.st.append((val, min(val, self.st[-1][1])))

    def pop(self) -> None:
        self.st.pop()

    def top(self) -> int:
        return self.st[-1][0]

    def getMin(self) -> int:
        return self.st[-1][1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()